package com.neusoft.sort.merge;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 归并排序
 * @date 2024-11-18
 */
public class MergeSort {

    /**
     * 归并排序: 时间复杂度 n(log^n)
     *
     * @param arr 待排序数组
     */
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length -1, new int[arr.length]);
    }

    public static void mergeSort(int[] arr, int leftIndex, int rightIndex, int[] tempArr) {
        if (leftIndex < rightIndex) {
            // 两个数组分割的中间数据索引下标
            int middleIndex = (leftIndex + rightIndex) / 2;
            // 向左递归进行分解
            mergeSort(arr, leftIndex, middleIndex, tempArr);
            // 向右递归进行分解
            mergeSort(arr, middleIndex + 1, rightIndex, tempArr);

            // 合并数组
            merge(arr, leftIndex, middleIndex, rightIndex, tempArr);
        }
    }

    /**
     * 按大小顺序合并两个数组
     *
     * @param arr            待排序数组
     * @param leftStartIndex 左边数组的开始数据索引下标
     * @param middleIndex    两个数组分割的中间数据索引下标
     * @param rightEndIndex  右边数组的结束数据索引下标
     * @param tempArr        临时数组
     */
    public static void merge(int[] arr, int leftStartIndex, int middleIndex, int rightEndIndex, int[] tempArr) {
        // 左边有序数组的初始索引
        int tempLeftStartIndex = leftStartIndex;
        // 右边有序数组的初始索引
        int tempRightStartIndex = middleIndex + 1;
        // 指向临时数组的初始索引
        int tempArrCurrentIndex = 0;

        // 先把左右两边(有序)的数组按大小顺序填充到temp数组, 直到左右两边的有序序列有一边处理完毕为止
        while (tempLeftStartIndex <= middleIndex && tempRightStartIndex <= rightEndIndex) {
            if (arr[tempLeftStartIndex] <= arr[tempRightStartIndex]) {
                // 如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素, 即将左边的当前元素，填充到临时数组
                tempArr[tempArrCurrentIndex] = arr[tempLeftStartIndex];
                tempLeftStartIndex++;
            } else {
                // 反之则将右边有序序列的当前元素，填充到临时数组
                tempArr[tempArrCurrentIndex] = arr[tempRightStartIndex];
                tempRightStartIndex++;
            }
            tempArrCurrentIndex++;
        }
        // 把有剩余数据的一边的数据依次全部填充到临时数组
        while (tempLeftStartIndex <= middleIndex) {
            tempArr[tempArrCurrentIndex] = arr[tempLeftStartIndex];
            tempLeftStartIndex++;
            tempArrCurrentIndex++;
        }
        while (tempRightStartIndex <= rightEndIndex) {
            tempArr[tempArrCurrentIndex] = arr[tempRightStartIndex];
            tempRightStartIndex++;
            tempArrCurrentIndex++;
        }
        // 将临时数组的元素拷贝到arr数组
        int roundTimes = rightEndIndex - leftStartIndex + 1;
        for (int i = 0; i < roundTimes; i++) {
            arr[leftStartIndex] = tempArr[i];
            leftStartIndex++;
        }
    }
}
